package leetcode_1100;

import java.util.Stack;

/**
 *@author 周杨 
 *RemoveAllAdjacentDuplicatesInString_1047 给一个数组 相邻相同的消除 问最后留下的字符串
 *describe:常规题 用栈 还有种方法 用原地数组 双指针记录留下的自负
 *2019年5月24日 上午11:20
 */
public class RemoveAllAdjacentDuplicatesInString_1047 {
	public String removeDuplicates(String S) {
         char[] chars = S.toCharArray();
         Stack<Character> stack = new  Stack<Character>();
         for(char c:chars) {
        	 if(!stack.isEmpty() && c == stack.peek()) {
        		 stack.pop();
        	 }else {
        		 stack.add(c);
        	 }
         }
         if(stack.isEmpty()) return "";
         StringBuilder sb = new StringBuilder(stack.size());
         while(!stack.isEmpty()) {
        	 sb.insert(0,stack.pop());
         }
         return sb.toString();
    }
}
